// QuickFillCtrler.cpp : implementation file
//

#include "stdafx.h"
#include "QuickFillCtrler.h"
#include "../ImageCores/Colors/ColorConverter.h"

//----------------------------------------------------------------------------
// Optimization / testing defines
//----------------------------------------------------------------------------

#ifdef QUICKFILL_SLOW
#define UPDATE_DISPLAY() \
if( m_bSlowMode && ::IsWindow(hWnd) ) { \
	m_DibData.SetDIBits(pBitmap); \
	::InvalidateRect(hWnd,NULL,FALSE); \
	::UpdateWindow(hWnd); \
}
#else
#define UPDATE_DISPLAY()
#endif // QUICKFILL_SLOW

// CQuickFillCtrler

CQuickFillCtrler::CQuickFillCtrler(CxImage* pImage, COLORREF fillColor, COLORREF borderColor)
{
	m_pVisitList = NULL;
	m_pLineList = NULL;		// List of lines to be visited.
	m_pFreeList = NULL;		// List of free nodes.
	m_bXSortOn = FALSE;		// X-Sorting flag (single visit indicator).
	m_bMemError = FALSE;	// Memory error flag.
	memset(&m_rcInvalid,0,sizeof(m_rcInvalid));
#ifdef QUICKFILL_SLOW
	m_bSlowMode = FALSE;	// Update active window and allow user to ESC
#endif
#ifdef QUICKFILL_TEST
	m_CurStackSize = 0U;	// Current number of nodes in line list.
	m_MaxStackSize = 0U;	// Greatest number of nodes added to line list.
	m_VisitSize = 0U;		// Number of nodes in the visited list
	m_CurrentLine  = 0;		// Current line being visited
	m_Direction = 0;		// Curent direction of travel
	m_nRevisitCount = 0;
	m_bShowRevisits = FALSE;
#endif

	this->m_fillColor = fillColor;
	this->m_borderColor = borderColor;
	this->m_pImage = pImage;
}

CQuickFillCtrler::~CQuickFillCtrler()
{
	// Safety only
	this->FreeLists();
}


// CQuickFillCtrler member functions

void CQuickFillCtrler::SetImage(CxImage *pImage)
{
	this->m_pImage = pImage;
}

CxImage* CQuickFillCtrler::GetImage()
{
	return this->m_pImage;
}

void CQuickFillCtrler::SetFillColor(COLORREF fillColor)
{
	this->m_fillColor = fillColor;
}

COLORREF CQuickFillCtrler::GetFillColor()
{
	return this->m_fillColor;
}

int CQuickFillCtrler::QuickFill(CPoint point, COLORREF fillColor)
{
	this->m_fillColor = fillColor;
	return this->QuickFill(point);
}

int CQuickFillCtrler::QuickFill(CPoint point)
{
	int minY, minX, maxY, maxX, dy;
	int childX1, childX2, parentX1, parentX2;
	int x = point.x;
	int y = point.y;

	/* Initialize global variables */
#ifdef QUICKFILL_TEST
	m_CurStackSize = m_MaxStackSize = m_VisitSize = 0U;
	m_nRevisitCount = m_CurrentLine = m_Direction = 0;
#endif
	m_bXSortOn = m_bMemError = FALSE;
	m_LastY = -1;

	/* Get seed pixel */
	RGBQUAD seedColor;
	m_pImage->GetPixelinBuffer(x, y, seedColor);
	CColorConverter* clrConverter = (CColorConverter*)m_pImage->GetColorConverter();
	DWORD seedColorValue = clrConverter->RGBtoDWORD(seedColor);
	
	// Initialize internal info based on fill type 
	if (m_borderColor != CLR_INVALID) 
	{
		// Check color at x,y position 
		if (seedColorValue == m_borderColor) 
			return -1;

		seedColorValue = m_borderColor;
		m_bXSortOn = TRUE;
	}

/* Using macros because we can not use pointers to non-static
 * member functions. This makes the code less efficient, but solves the problem.
 */
#define FindLeft(x,y,xmin,color) \
	((m_borderColor != CLR_INVALID) \
	? SearchLeft(x,y,xmin,color) : ScanLeft(x,y,xmin,color))
#define FindRight(x,y,xmax,color) \
	((m_borderColor != CLR_INVALID) \
	? SearchRight(x,y,xmax,color) : ScanRight(x,y,xmax,color))
#define SkipRight(x,y,xmax,color) \
	((m_borderColor != CLR_INVALID) \
	? ScanRight(x,y,xmax,color) : SearchRight(x,y,xmax,color))
	
	// Initialize Line list
	if (this->CreateFreeList())
		return -2;
	// Initialize coordinates
	maxX = m_pImage->GetWidth() - 1;
	maxY = m_pImage->GetHeight() - 1;
	minX = minY = 0;

	CRect workingRect(minX, minY, maxX, maxY);
	if (m_pImage->GetWorkingArea())
	{
		workingRect = m_pImage->GetWorkingArea()->BoundingRectangle();
		if (workingRect.left > 0 && workingRect.left < maxX)
			minX = workingRect.left;
		if (workingRect.right > 0 && workingRect.right < maxX)
			maxX = workingRect.right;
		if (workingRect.top > 0 && workingRect.top < maxY)
			minY = workingRect.top;
		if (workingRect.bottom > 0 && workingRect.bottom < maxY)
			maxY = workingRect.bottom;
	}

	if (x < minX || x > maxX || y < minY || y > maxY)
		return -1;

	/* Initialize invalid rectangle */
	m_rcInvalid.left = m_rcInvalid.right  = x;
	m_rcInvalid.top  = m_rcInvalid.bottom = y;

	/* Push starting point on stack.
	 * Durring testing calling FindLeft() & FindRight() here reduced the number
	 * of revisits by 1 and the number of items on the visit list by 2.
	 */
	childX1 = FindLeft(x, y, minX, seedColorValue) + 1;
	childX2 = FindRight(x, y, maxX, seedColorValue) - 1;
	this->PushLine(childX1, childX2, y, +1); // Needed in one special case 
	this->PushLine(childX1, childX2, ++y,-1);

	// Now start flooding
	while (m_pLineList)
	{
		this->PopLine(parentX1, parentX2, y, dy);
		y += dy;
#ifdef QUICKFILL_TEST
		m_CurrentLine = y;
		m_Direction = dy;
#endif
		if (y < minY || y > maxY)
			continue;
		if (m_bMemError)
			continue;
		if (m_bXSortOn && IsRevisit(parentX1, parentX2, y))
			continue;
		
		// This slows things down a little but provides needed information
		if (parentX1 < m_rcInvalid.left)
			m_rcInvalid.left = parentX1;
		else if (parentX2 > m_rcInvalid.right)
			m_rcInvalid.right = parentX2;
		if (y < m_rcInvalid.top)
			m_rcInvalid.top = y;
		else if (y > m_rcInvalid.bottom)
			m_rcInvalid.bottom = y;

#ifdef QUICKFILL_SLOW
		if( m_bSlowMode ) {
			if( ::GetAsyncKeyState(VK_ESCAPE) < 0 )
				break;
		}
#endif

		// Find ChildLeft end (ChildLeft>ParentLeft on failure)
		childX1 = FindLeft(parentX1, y, minX, seedColorValue) + 1;
		if (childX1 <= parentX1)
		{
			// Find ChildRight end (this should not fail here)
			childX2 = FindRight(parentX1 + 1, y, maxX, seedColorValue) - 1;
			// Fill line
			for (int i = childX1; i <= childX2; i++)
				m_pImage->SetPixelinBuffer(i, y, m_fillColor);

			UPDATE_DISPLAY();
			// Push unvisited lines
			if (childX1 >= parentX1 - 1 && childX2 <= parentX2 + 1)
			{
				/* No reverse clipping required
				 *
				 * Example: Going down
				 * +-------------+
				 * |xxxxxxxxxxxxx|
				 * +---+xxxxx+---+
				 * |   |xxxxx|	 |   <- Parent Line (CASE 1)
				 * |   |xxxxx|	 |   <- Child Line
				 * |   |xxxxx|   |
				 * |  ++xxxxx++  |   <- Parent Line (CASE 2)
				 * |  |xxxxxxx|  |   <- Child Line
				 * +--+-------+--+
				 */
				PushLine(childX1, childX2, y, dy);
			}
			else {
				if(m_bXSortOn)
					PushOpposite(parentX1, parentX2, childX1, childX2 ,y, dy);

#ifndef QUICKFILL_NO_REVERSE_CLIP_OPT // Reduces total number of pixels visited
				else if (childX1 == parentX1) 
				{
					/* Reverse clip left
					 *
					 * Example: Going up
					 * +-----------------+
					 * |xxxxxxxxxxxxxxxxx|   <- Child Line
					 * |xxx+----+   +----+   <- Parent Line
					 * |xxx|    |   |    |
					 * +---+----+---+----+
					 */
					PushLine(parentX2 + 2, childX2, y, -dy);
				}
				else if (childX2 == parentX2) 
				{
					/* Reverse clip right
					 *
					 * Example: Going up
					 * +-----------------+
					 * |xxxxxxxxxxxxxxxxx|   <- Child Line
					 * +----+   +----+xxx|   <- Parent Line
					 * |    |   |    |xxx|
					 * +----+---+----+---+
					 */
					PushLine(childX1, parentX1 - 2, y, -dy);
				}
#endif
				else
				{
					/* Normal reverse push
					 *
					 * Example: Going up
					 * +-------------------+
					 * |xxxxxxxxxxxxxxxxxxx| <- Child Line
					 * +   +---+xxx+---+   | <- Parent Line
					 * |   |   |xxx|   |   |
					 * +---+---+---+---+---+
					 */
					PushLine(childX1, childX2, y, -dy);
				}
				PushLine(childX1, childX2, y, dy);
			}
			/* Addvance ChildRight end on to border */
			++childX2;
		}
		else childX2 = parentX1;

		// Fill betweens
		while (childX2 < parentX2) 
		{
			// Skip to new ChildLeft end (ChildRight>ParentRight on failure) 
			childX2 = SkipRight(childX2 + 1, y, parentX2, seedColorValue);
			// If new ChildLeft end found 
			if (childX2 <= parentX2)
			{
				childX1 = childX2;

				// Find ChildRight end (this should not fail here)
				childX2 = FindRight(childX1 + 1, y, maxX, seedColorValue) - 1;

				// Fill line
				for (int i = childX1; i <= childX2; i++)
					m_pImage->SetPixelinBuffer(i, y, m_fillColor);

				UPDATE_DISPLAY();

				// Push unvisited lines
				if (childX2 <= parentX2 + 1)
					PushLine(childX1, childX2, y, dy);

				else 
				{
					if (m_bXSortOn)
						PushOpposite(parentX1, parentX2, childX1, childX2, y, dy);
					else
						PushLine(childX1, childX2, y, -dy);
					PushLine(childX1, childX2, y, dy);
				}
				// Addvance ChildRight end onto border
				++childX2;
			}
		}
	}

#ifdef QUICKFILL_TEST
	if( m_bShowRevisits && m_nRevisitCount ) // only if revisit occured
	{
		HLINE_NODE*	pNext = m_pVisitList;
		while( pNext ) {
			m_DibData.DrawLineH(pNext->x1,pNext->x2,pNext->y,DWORD(pNext->dy));
			pNext = pNext->pNext;
		}
	}
#endif // QUICKFILL_TEST
	
	this->FreeLists();
	return (m_bMemError ? -2 : 0);
}

BOOL CQuickFillCtrler::CreateFreeList()
{
	// allocate one node sized list
	m_pFreeList = (HLINE_NODE*)calloc(1,sizeof(HLINE_NODE));
	return (m_pFreeList == NULL);
}

void CQuickFillCtrler::FreeLists()
{
	HLINE_NODE *pNext;
	while(m_pFreeList) {
		pNext = m_pFreeList->pNext;
	  	free(m_pFreeList);
	  	m_pFreeList = pNext;
	}

	while(m_pLineList) {
		pNext = m_pLineList->pNext;
	  	free(m_pLineList);
	  	m_pLineList = pNext;
	}
	
	while(m_pVisitList) {
		pNext = m_pVisitList->pNext;
	  	free(m_pVisitList);
	  	m_pVisitList = pNext;
	}
}

// simulate a stack operation in a linked list
void CQuickFillCtrler::PushLine(int x1, int x2, int y, int dy)
{
	HLINE_NODE *pNew = m_pFreeList;
	if (pNew)
		m_pFreeList = m_pFreeList->pNext;
	else
		pNew = (HLINE_NODE*)calloc(1,sizeof(HLINE_NODE));
	/* Add to start of list */
	if (pNew) 
	{
		pNew->x1 = x1;
		pNew->x2 = x2;
		pNew->y  = y;
		pNew->dy = dy;
		
		if (m_bXSortOn) 
		{
			/* This is for the single line visiting code.
			 * The code runs about 18% slower but you can
			 * use fill patterns with it.
			 * Since the basic algorithym scans lines from
			 * left to right it is required that the list
			 * be sorted from left to right.
			 */
			HLINE_NODE *pThis,*pPrev=(HLINE_NODE*)0;
			for (pThis = m_pLineList; pThis; pThis = pThis->pNext) 
			{
				if (x1 <= pThis->x1)
					break;
				pPrev = pThis;
			}
			if (pPrev) 
			{
				pNew->pNext = pPrev->pNext;
				pNew->pPrev = pPrev;
				pPrev->pNext = pNew;
				if (pNew->pNext)
					pNew->pNext->pPrev = pNew;
			}
			else 
			{
				pNew->pNext = m_pLineList;
				pNew->pPrev = (HLINE_NODE*)0;
				if (pNew->pNext)
					pNew->pNext->pPrev = pNew;
				m_pLineList = pNew;
			}
		}
		else 
		{
			pNew->pNext = m_pLineList;
			m_pLineList = pNew;
		}
#ifdef QUICKFILL_TEST
		++m_CurStackSize;
		if( m_CurStackSize > m_MaxStackSize )
			m_MaxStackSize = m_CurStackSize;
#endif
	}
	else m_bMemError = 1;
}

// simulate a stack operation in a linked list
void CQuickFillCtrler::PopLine(int &x1, int &x2, int &y, int &dy)
{
	if (m_pLineList)
	{
		HLINE_NODE *pThis,*pPrev;
		/* Search lines on stack for same line as last line.
		 * This smooths out the flooding of the graphics object
		 * and reduces the size of the stack. */
		pPrev = m_pLineList;
		for (pThis = m_pLineList->pNext; pThis; pThis = pThis->pNext) 
		{
			if (pThis->y == m_LastY)
				break;
			pPrev = pThis;
		}
		/* If pThis found - remove it from list */
		if (pThis) {
			pPrev->pNext = pThis->pNext;
			if( pPrev->pNext )
				pPrev->pNext->pPrev = pPrev;
			x1 = pThis->x1;
			x2 = pThis->x2;
			y  = pThis->y;
			dy = pThis->dy;
		}
		/* Remove from start of list */
		else 
		{
			x1 = m_pLineList->x1;
			x2 = m_pLineList->x2;
			y  = m_pLineList->y;
			dy = m_pLineList->dy;
			pThis = m_pLineList;
			m_pLineList = m_pLineList->pNext;
			if (m_pLineList)
				m_pLineList->pPrev = (HLINE_NODE*)0;
		}

		pThis->pNext = m_pFreeList;
		m_pFreeList = pThis;
#ifdef QUICKFILL_TEST
		--m_CurStackSize;
#endif
		m_LastY = y;
	}
}

void CQuickFillCtrler::PushVisitedLine(int x1, int x2, int y)
{
	HLINE_NODE *pNew = m_pFreeList;
	if (pNew)
		m_pFreeList = m_pFreeList->pNext;
	else
		pNew = (HLINE_NODE*)calloc(1,sizeof(HLINE_NODE));
	/* Add to start of list */
	if (pNew)
	{
		pNew->x1 = x1;
		pNew->x2 = x2;
		pNew->y  = y;
#ifdef QUICKFILL_TEST
		pNew->dy  = (int)m_DibData.RGBtoValue(RGB(0,255,255));
#endif
		pNew->pNext = m_pVisitList;
		m_pVisitList = pNew;
#ifdef QUICKFILL_TEST
		++m_VisitSize;
#endif
	}
	else m_bMemError = 1;
}

/* Checks if line has already been visited */
BOOL CQuickFillCtrler::IsRevisit(int x1, int x2, int y)
{
	HLINE_NODE* pNext = m_pVisitList;
	while (pNext)
	{
		if( pNext->y == y && pNext->x1 <= x1 && x2 <= pNext->x2 )
		{
#ifdef QUICKFILL_TEST
			if (!m_pFreeList) // do to where IsRevisit() is called
				pNext->dy = (int)m_DibData.RGBtoValue(RGB(0,255,0));
			else 
			{
				int nColor;
				if (m_pFreeList->dy < 0)
					nColor = (int)m_DibData.RGBtoValue(RGB(255,255,0));
				else
					nColor = (int)m_DibData.RGBtoValue(RGB(0,0,255));
				// tack on end for drawing
				while( pNext->pNext )
					pNext = pNext->pNext;
				HLINE_NODE *pNew = m_pFreeList;
				m_pFreeList = m_pFreeList->pNext;
				pNew->x1 = x1;
				pNew->x2 = x2;
				pNew->y  = y;
				pNew->dy = nColor;
				pNew->pNext = NULL;
				pNext->pNext = pNew;
			}
			++m_nRevisitCount;
#endif
			break;
		}
		pNext = pNext->pNext;
	}
	return (pNext != NULL);
}

/* Find next line segment on parent line.
 * Note: This function is designed to be
 *		called until NULL is returned.
 */
CQuickFillCtrler::HLINE_NODE* CQuickFillCtrler::FindNextLine(int x1, int x2, int y)
{
	static HLINE_NODE *pFindNext=(HLINE_NODE*)0;
	HLINE_NODE *pThis;
	if (!pFindNext)
		pFindNext = m_pLineList;

	for (pThis = pFindNext; pThis; pThis = pThis->pNext)
	{
		if ((pThis->y + pThis->dy) == y) 
		{
			if (x1 < pThis->x1 && pThis->x1 <= x2)
			{
				pFindNext = pThis->pNext;
				return pThis;
			}
		}
	}
	return (pFindNext=(HLINE_NODE*)0);
}

/* Removes pThis from line list */
void CQuickFillCtrler::PopThis(HLINE_NODE *pThis)
{
	if( m_pLineList ) {
		/* If pThis is not start of list */
		if( pThis->pPrev ) {
			HLINE_NODE *pPrev = pThis->pPrev;
			pPrev->pNext = pThis->pNext;
			if( pPrev->pNext )
				pPrev->pNext->pPrev = pPrev;
		}
		/* Remove pThis from start of list */
		else {
			m_pLineList = m_pLineList->pNext;
			if( m_pLineList )
				m_pLineList->pPrev = (HLINE_NODE*)0;
		}
		pThis->pNext = m_pFreeList;
		m_pFreeList = pThis;
#ifdef QUICKFILL_TEST
		--m_CurStackSize;
#endif
	}
}

/* Push unvisited lines onto the stack
 *
 * +-----------------------------------+
 * |                                   |
 * +---+   +---+   +---+   +---+   +---+
 * |   |   |   |   |   |   |   |   |   |
 * |   |(..+---+...+---+...+---+..)|   | <- Pushed Up
 * |   |xxxxxxxxxxxxxSxxxxxxxxxxxxx|   | <- Drawn
 * +---+(-------------------------)+---+ <- Pushed Down
 *
 * +-----------------------------------+
 * |                                   |
 * +---+   +---+   +---+   +---+   +---+
 * |   |(.)|   |(.)|   |(.)|   |(.)|   | <- Pushed Up
 * |   |xxx+...+xxx+...+xxx+...+xxx|   | <- Drawn
 * |   |xxxxxxxxxxxxxxxxxxxxxxxxxxx|   |
 * +---+---------------------------+---+
 *
 * +-----------------------------------+
 * |                                   |
 * +---+(.)+---+(.)+---+(.)+---+(.)+---+ <- Pushed Up
 * |   |xxx|   |xxx|   |xxx|   |xxx|   | <- Drawn
 * |   |xxx+---+xxx+---+xxx+---+xxx|   |
 * |   |xxxxxxxxxxxxxxxxxxxxxxxxxxx|   |
 * +---+---------------------------+---+
 *
 * +-----------------------------------+
 * |    (.)     (.)     (.)     (.)    | <- Pushed Up
 * +---+xxx+---+xxx+---+xxx+---+xxx+---+ <- Drawn
 * |   |xxx|   |xxx|   |xxx|   |xxx|   |
 * |   |xxx+---+xxx+---+xxx+---+xxx|   |
 * |   |xxxxxxxxxxxxxxxxxxxxxxxxxxx|   |
 * +---+---------------------------+---+
 *
 * +(---------------------------------)+ <- Pushed Up
 * |xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx| <- Drawn
 * +(-)+xxx+(-)+xxx+(-)+xxx+(-)+xxx+(-)+ <- Pushed Down (PushOpposite)
 * |   |xxx|   |xxx|   |xxx|   |xxx|   |
 * |   |xxx+---+xxx+---+xxx+---+xxx|   |
 * |   |xxxxxxxxxxxxxxxxxxxxxxxxxxx|   |
 * +---+---------------------------+---+
 */
void CQuickFillCtrler::PushOpposite(int OldX1, int OldX2, int x1, int x2, int y, int dy)
{
	/* Find next line on parent line */
	HLINE_NODE *pFind = FindNextLine(x1,x2,y);
	if (!pFind)
	{
		/* push cliped left ends */
		if (x1 < --OldX1)
			PushLine(x1, --OldX1, y, -dy);
		if (x2 > ++OldX2)
			PushLine(++OldX2, x2, y, -dy);
	}
	else 
	{
		/* push cliped left */
		if (x1 < --OldX1)
			PushLine(x1, --OldX1, y, -dy);
		/* set test value for right cliping */
		OldX1 = x2+1;
		do 
		{
			/* push valid line only */
			if (++OldX2 < pFind->x1 - 2)
				PushLine(++OldX2, pFind->x1-2, y, -dy);
			OldX2 = pFind->x2;
			/* clip right end if needed */
			if (OldX2 > OldX1)
				pFind->x1 = ++OldX1;
			
			else /* pop previously visited line */
				PopThis(pFind);
			pFind = FindNextLine(x1, x2, y);
		} while (pFind);

		/* Special Cases
		 *
		 * S = Seed point
		 * x = Filled point
		 * o = Unfilled point
		 *
		 * CASE 1:                CASE 2: Indirectly solved by
		 *                                the solution to case 1.
		 * +-----------------+    +-----------------+
		 * |xxxxxxxxxxxxxxxxx|    |xxxxxxxxxxxxxxxxx|
		 * |x+-----+x+-----+x|    |x+-----+x+-----+x|
		 * |x|xxxxx|x|x|x|x|x|    |x|xxxxx|x|x|x|x|x|
		 * |x|x|x|x|x|x|x|x|x|    |x|x|x|x|x|x|x|x|x|
		 * |x|x|x|x|x|x|x|x|x|    |x|x|x|x|x|x|x|x|x|
		 * |x|x|x|x|x|x|x|x|x|    |x|x|x|x|x|x|x|x|x|
		 * |xxxxxxxxxxxxxxx|x|    |xxxxxxxSxxxxxxx|x|
		 * |x|x|x|x|x|o|o|o|x|    |x|x|x|o|x|x|x|x|x|
		 * |x|x|x|x|x|o|o|o|x|    |x|x|x|o|x|x|x|x|x|
		 * |x|x|x|x|x|o|o|o|x|    |x|x|x|o|x|x|x|x|x|
		 * |x|xxxxx|x|o|o|o|x|    |x|xxxxx|x|x|x|x|x|
		 * |x+-----+x+-----+x|    |x+-----+x+-----+x|
		 * |xxxxxxxxxxxxxxxxS|    |xxxxxxxxxxxxxxxxx|
		 * +-----------------+    +-----------------+
		 *
		 */
		if (++OldX2 < x2)
			PushLine(OldX2, x2, y, -dy);
	}
	PushVisitedLine(x1, x2, y);
}


static BYTE lgs_Mask8[8] = {0x80,0x40,0x20,0x10,0x08,0x04,0x02,0x01};
static BYTE lgs_Mask4[4] = {0xC0,0x30,0x0C,0x03};
static BYTE lgs_Mask2[2] = {0xF0,0x0F};

/*
Searches for value that is not equal to given color value.

\returns
Greater than or equal to xmax value on success; otherwise
less than xmax on failure.
*/
int CQuickFillCtrler::ScanLeft(
						int x,			//!< x-coordinate.
						int y,			//!< y-coordinate.
						int xmin,		//!< x-minimum coordinate
						DWORD dwValue	//!< Specifies color value.
						)
{
	LONG width = m_pImage->GetWidth();
	// error
	if (x < 0 || x >= width || y < 0 || y >= m_pImage->GetHeight())
		return --xmin;
	if (dwValue == CLR_INVALID || xmin >= width)
		return --xmin;

	LPBYTE addr = (LPBYTE)m_pImage->GetPixelAddress(x, y);
	int bpp = m_pImage->GetBPP();
	switch (bpp)
	{
	case 1:
		if (dwValue)
			dwValue == 0xFF;
		for (; x >= xmin; addr--)
		{
			for (int i = (x & 7); i >= 0; i--, x--)
			{
				if (BYTE(dwValue & lgs_Mask8[i]) != (*addr & lgs_Mask8[i]))
					return x;
			}
		}
		break;
	case 2:
		dwValue |= (dwValue << 2) | (dwValue << 4) | (dwValue << 6);
		for (; x >= xmin; addr--)
		{
			for (int i = (x & 3); i >= 0; i--, x--)
			{
				if (BYTE(dwValue & lgs_Mask4[i]) != (*addr & lgs_Mask4[i]))
					return x;
			}
		}
		break;
	case 4:
		dwValue |= (dwValue << 4);
		for (; x >= xmin; addr--)
		{
			for (int i = (x & 1); i >= 0; i--, x--)
			{
				if (BYTE(dwValue & lgs_Mask2[i]) != (*addr & lgs_Mask2[i]))
					return x;
			}
		}
		break;
	case 8:
		for (; x >= xmin; x--, addr--)
		{
			if (BYTE(dwValue) != *addr)
				break;
		}
		break;
	case 16:
		for (; x >= xmin; x--, addr -= 2)
		{
			if (WORD(dwValue) != *(LPWORD)addr)
				break;
		}
		break;
	case 24:
		for (; x >= xmin; x--, addr -= 3)
		{
			//if (*(RGBTRIPLE*)&dwValue != *(RGBTRIPLE*)addr)
			if (dwValue != (0x00FFFFFF & *(LPDWORD)addr))
				break;
		}
		break;
	case 32:
		for (; x >= xmin; x--, addr -= 4)
		{
			if (dwValue != *(LPDWORD)addr)
				break;
		}
		break;
	}
	return x;
}

/*
Searches for value that is not equal to given color value.

\returns
Less than or equal to xmax value on success; otherwise
greater than xmax on failure.
*/
int CQuickFillCtrler::ScanRight(
						int x,			//!< x-coordinate.
						int y,			//!< y-coordinate.
						int xmax,		//!< x-minimum coordinate
						DWORD dwValue	//!< Specifies color value.
						)
{
	LONG width = m_pImage->GetWidth();
	// error
	if (x < 0 || x >= width || y < 0 || y >= m_pImage->GetHeight())
		return ++xmax;
	if (dwValue == CLR_INVALID || xmax >= width)
		return ++xmax;

	LPBYTE addr = (LPBYTE)m_pImage->GetPixelAddress(x, y);
	int bpp = m_pImage->GetBPP();
	switch (bpp)
	{
	case 1:
		if (dwValue)
			dwValue == 0xFF;
		for (; x <= xmax; addr++)
		{
			for (int i = (x & 7); i < 8; i++, x++)
			{
				if (BYTE(dwValue & lgs_Mask8[i]) != (*addr & lgs_Mask8[i]))
					return x;
			}
		}
		break;
	case 2:
		dwValue |= (dwValue << 2) | (dwValue << 4) | (dwValue << 6);
		for (; x <= xmax; addr++)
		{
			for (int i = (x & 3); i < 4; i++, x++)
			{
				if (BYTE(dwValue & lgs_Mask4[i]) != (*addr & lgs_Mask4[i]))
					return x;
			}
		}
		break;
	case 4:
		dwValue |= (dwValue << 4);
		for (; x <= xmax; ++addr)
		{
			for (int i = (x & 1); i < 2; i++, x++)
			{
				if (BYTE(dwValue & lgs_Mask2[i]) != (*addr & lgs_Mask2[i]))
					return x;
			}
		}
		break;
	case 8:
		for (; x <= xmax; x++, addr++)
		{
			if (BYTE(dwValue) != *addr)
				break;
		}
		break;
	case 16:
		for (; x <= xmax; x++, addr += 2)
		{
			if (WORD(dwValue) != *(LPWORD)addr)
				break;
		}
		break;
	case 24:
		for (; x <= xmax; x++, addr += 3)
		{
			//if (*(RGBTRIPLE*)&dwValue != *(RGBTRIPLE*)addr)
			if (dwValue != (0x00FFFFFF & *(LPDWORD)addr))
				break;
		}
		//// when x = xmax, deal with it
		//if (x == xmax &&
		//	dwValue == *(addr) /*b*/ |
		//	*(addr+1) << 8/*g*/ |
		//	*(addr+2) << 16/*r*/)
		//{
		//	x++;
		//	addr += 3;
		//}
		break;
	case 32:
		for (; x <= xmax; x++, addr += 4)
		{
			if (dwValue != *(LPDWORD)addr)
				break;
		}
		break;
	}
	return x;
}

/*
Searches for value that is equal to given color value.

\returns
Greater than or equal to xmax value on success; otherwise
less than xmax on failure.
*/
int CQuickFillCtrler::SearchLeft(
						int x,			//!< x-coordinate.
						int y,			//!< y-coordinate.
						int xmin,		//!< x-minimum coordinate
						DWORD dwValue	//!< Specifies color value.
						)
{
	LONG width = m_pImage->GetWidth();
	// error
	if (x < 0 || x >= width || y < 0 || y >= m_pImage->GetHeight())
		return --xmin;
	if (dwValue == CLR_INVALID || xmin >= width)
		return --xmin;
	
	LPBYTE addr = (LPBYTE)m_pImage->GetPixelAddress(x, y);
	int bpp = m_pImage->GetBPP();
	switch (bpp)
	{
	case 1:
		if (dwValue)
			dwValue == 0xFF;
		for (; x >= xmin; addr--)
		{
			for (int i = (x & 7); i >= 0; i--, x--)
			{
				if (BYTE(dwValue & lgs_Mask8[i]) == (*addr & lgs_Mask8[i]))
					return x;
			}
		}
		break;
	case 2:
		dwValue |= (dwValue << 2) | (dwValue << 4) | (dwValue << 6);
		for (; x >= xmin; addr--)
		{
			for (int i = (x & 3); i >= 0; i--, x--)
			{
				if (BYTE(dwValue & lgs_Mask4[i]) == (*addr & lgs_Mask4[i]))
					return x;
			}
		}
		break;
	case 4:
		dwValue |= (dwValue << 4);
		for (; x >= xmin; addr--)
		{
			for (int i = (x & 1); i >= 0; i--, x--)
			{
				if (BYTE(dwValue & lgs_Mask2[i]) == (*addr & lgs_Mask2[i]))
					return x;
			}
		}
		break;
	case 8:
		for (; x >= xmin; x--, addr--)
		{
			if (BYTE(dwValue) == *addr)
				break;
		}
		break;
	case 16:
		for (; x >= xmin; x--, addr -= 2)
		{
			if (WORD(dwValue) == *(LPWORD)addr)
				break;
		}
		break;
	case 24:
		for (; x >= xmin; x--, addr -= 3)
		{
			//if (*(RGBTRIPLE*)&dwValue == *(RGBTRIPLE*)addr)
			if (dwValue == (0x00FFFFFF & *(LPDWORD)addr))
				break;
		}
		break;
	case 32:
		for (; x >= xmin; x--, addr -= 4)
		{
			if (dwValue == *(LPDWORD)addr)
				break;
		}
		break;
	}
	return x;
}

/*
Searches for value that is equal to given color value.

\returns
Less than or equal to xmax value on success; otherwise
greater than xmax on failure.
*/
int CQuickFillCtrler::SearchRight(
						int x,			//!< x-coordinate.
						int y,			//!< y-coordinate.
						int xmax,		//!< x-minimum coordinate
						DWORD dwValue	//!< Specifies color value.
						)
{
	LONG width = m_pImage->GetWidth();
	// error
	if (x < 0 || x >= width || y < 0 || y >= m_pImage->GetHeight())
		return ++xmax;
	if (dwValue == CLR_INVALID || xmax >= width)
		return ++xmax;

	LPBYTE addr = (LPBYTE)m_pImage->GetPixelAddress(x, y);
	int bpp = m_pImage->GetBPP();
	switch (bpp)
	{
	case 1:
		if (dwValue)
			dwValue == 0xFF;
		for (; x <= xmax; addr++)
		{
			for (int i = (x & 7); i < 8; i++, x++)
			{
				if (BYTE(dwValue & lgs_Mask8[i]) == (*addr & lgs_Mask8[i]))
					return x;
			}
		}
		break;
	case 2:
		dwValue |= (dwValue << 2) | (dwValue << 4) | (dwValue << 6);
		for (; x <= xmax; addr++)
		{
			for (int i = (x & 3); i < 4; i++, x++)
			{
				if (BYTE(dwValue & lgs_Mask4[i]) == (*addr & lgs_Mask4[i]))
					return x;
			}
		}
		break;
	case 4:
		dwValue |= (dwValue << 4);
		for (; x <= xmax; ++addr)
		{
			for (int i = (x & 1); i < 2; i++, x++)
			{
				if (BYTE(dwValue & lgs_Mask2[i]) == (*addr & lgs_Mask2[i]))
					return x;
			}
		}
		break;
	case 8:
		for (; x <= xmax; x++, addr++)
		{
			if (BYTE(dwValue) == *addr)
				break;
		}
		break;
	case 16:
		for (; x <= xmax; x++, addr += 2)
		{
			if (WORD(dwValue) == *(LPWORD)addr)
				break;
		}
		break;
	case 24:
		for (; x <= xmax; x++, addr += 3)
		{
			//if (*(RGBTRIPLE*)&dwValue == *(RGBTRIPLE*)addr)
			if (dwValue == (0x00FFFFFF & *(LPDWORD)addr))
				break;
		}
		//// when x = xmax, deal with it
		//if (x == xmax &&
		//	dwValue == *(addr) /*b*/ |
		//	*(addr+1) << 8/*g*/ |
		//	*(addr+2) << 16/*r*/)
		//{
		//	x++;
		//	addr += 3;
		//}
		break;
	case 32:
		for (; x <= xmax; x++, addr += 4)
		{
			if (dwValue == *(LPDWORD)addr)
				break;
		}
		break;
	}
	return x;
}